package otherBefore.month05;

import java.util.*;

/**
 * @author sps
 * @date 2023/5/10 9:22
 */
public class leetcode {

    public static void main(String[] args) {
        String str = "";
        String[] strArr = str.split(";");
        System.out.println("01:15".compareTo("01:00"));
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    int min = Integer.MAX_VALUE, last = Integer.MIN_VALUE;
    public int getMinimumDifference(TreeNode root) {
        dfsRoot(root);
        return min;
    }

    private void dfsRoot(TreeNode root) {
        if(root==null)return;
        dfsRoot(root.left);
        min = Math.min(min, root.val - last);
        last = root.val;
        dfsRoot(root.right);
    }

    public int numTilePossibilities(String tiles) {
        Map<Character, Integer> count = new HashMap<>();
        for(int i=0; i<tiles.length(); i++){
            count.put(tiles.charAt(i),count.getOrDefault(tiles.charAt(i),0)+1);
        }
        Set<Character> set = new HashSet<>(count.keySet());
        return dfs(tiles.length(),count,set);
    }

    private int dfs(int length, Map<Character, Integer> count, Set<Character> set) {
        if(length == 0)return 1;
        int res = 1;
        for (Character c : set) {
            if(count.get(c) > 0){
                count.put(c,count.get(c)-1);
                res += dfs(length - 1,count,set);
                count.put(c,count.get(c)+1);
            }
        }
        return res;
    }

    List<Integer> list = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        preNode(root);
        return list;
    }

    private void preNode(Node root) {
        if(root == null)return;
        list.add(root.val);
        for (Node child : root.children) {
            preNode(child);
        }
    }

    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int an1 = arr1.length, an2 = arr2.length;
        List<Integer> list = new ArrayList<>();
        int last = 0;
        while ((an1 > 0 || an2 > 0) && last == 0){
            int a = an1 > 0 ? arr1[an1 - 1] : 0;
            int b = an2 > 0 ? arr2[an2 - 1] : 0;
            int cur = a + b + last;
            if(cur == 2){
                last = -1;
                list.add(0);
            }else if (cur == 1){
                last = 0;
                list.add(1);
            }else if (cur == -1){
                last = 1;
                list.add(1);
            }else if (cur == 3){
                last = -1;
                list.add(1);
            }else if (cur == 0){
                last = 0;
                list.add(0);
            }
            an1--;an2--;
        }
        for(int i=list.size()-1; i>=0; i--){
            if(list.get(i) == 0){
                list.remove(i);
            }
        }
        int[] ans = new int[list.size()];
        for(int i=list.size()-1; i>=0; i--){
            ans[i] = list.get(i);
        }
        return ans;
    }

    public int[] findMode(TreeNode root) {
        return new int[]{0};
    }

    public int maxDepth(Node root) {
        if(root == null)return 0;
        List<Node> children = root.children;
        int ans = 1;
        for (Node child : children) {
            int d = maxDepth(child);
            ans = Math.max(ans,d);
        }
        return ans;
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    public int islandPerimeter(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                for(int k=0; k<4; k++){
                    int ix = i + dx[k];
                    int jy = j + dy[k];
                    if(ix<0 || ix >=n || jy<0 || jy>=m || grid[ix][jy] == 0){
                        ans++;
                    }

                }
            }
        }
        return ans;
    }

    public int leastMinutes(int n) {
        int ans = 0, cur = 1;
        while (n > cur * 2){
            ans++;
        }
        return ans;
    }

    public boolean haveConflict(String[] event1, String[] event2) {
        if(event2[0].compareTo(event1[0]) >= 0 && event2[0].compareTo(event1[1]) <= 0){
            return true;
        }
        if(event2[0].compareTo(event1[0]) <= 0 && event2[1].compareTo(event1[0]) >= 0){
            return true;
        }
        return false;
    }

    /**
     * 给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
     * @param num
     * @return
     */
    public int reverseBits(int num) {
        int ans = 0;
        //把整数装换成二进制字符串，前面拼接0是为了处理7(111)这种场景
        String s = Integer.toBinaryString(num);
        if(s.length() < 32){
            s = "0" + s;
        }
        //利用双指针算法，x是左指针，i是右指针，cur为x-i之间0的个数。只有当cur==0的时候我们计算ans = Math.max(ans,i-x+1);
        int x = 0, cur = 0;
        for (int i=0; i<s.length(); i++){
            if(s.charAt(i) == '0'){
                cur++;
            }
            while (cur>1 && x < i){
                if(s.charAt(x) == '0'){
                    cur--;
                }
                x++;
            }
            ans = Math.max(ans,i-x+1);
        }

        return ans;
    }

    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        dp[0] = cost[0]; dp[1] = cost[1];
        for (int i=2; i<n; i++){
            dp[i] = cost[i] + Math.min(dp[i-1],dp[i-2]);
        }
        return Math.min(dp[n-1],dp[n-2]);
    }


    public int[] countBits(int n) {
        int[] ans = new int[n+1];
        int hei = 0;
        for(int i=0; i<n; i++){
            if((i & (i-1)) == 0){
                hei = i;
            }
            ans[i] = ans[i-hei] + 1;
        }
        return ans;
    }

    private int countN(int x) {
        int count = 0;
        while (x > 0){
            x &= (x-1);
            count++;
        }
        return count;
    }


    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if(n < d)return -1;
        int[][] dp = new int[d][n];

        for (int[] ints : dp) {
            Arrays.fill(ints,Integer.MAX_VALUE);
        }
        dp[0][0] = jobDifficulty[0];
        for (int i=1; i<n; i++) {
            dp[0][i] = Math.max(dp[0][i-1],jobDifficulty[i]);
        }
        for (int i=1; i<d; i++){
            for (int j=i; j<n; j++){
                int cur = 0;
                for(int k=j; k<n; k++){
                    cur = Math.max(cur,jobDifficulty[k]);
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1]+cur);
                }
            }
        }

        return dp[d-1][n-1];
    }


    public int maxEqualRowsAfterFlips(int[][] matrix) {
        int ans = 0;
        Map<String, Integer> matrixMap = new HashMap<>();
        int n = matrix.length;
        for(int i=0; i<n; i++){
            StringBuilder sb = new StringBuilder();
            for(int j=0; j<matrix[0].length; j++) {
                sb.append((char) ('0' + (matrix[i][j] ^ matrix[i][0])));
            }
            matrixMap.put(sb.toString(),matrixMap.getOrDefault(sb.toString(),0)+1);

            ans = Math.max(ans,matrixMap.get(sb.toString()));
        }

        return ans;
    }

    public int findMaxK(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int ans = 0;
        for(int i=0; i<nums.length; i++){
            if(set.contains(-nums[i])){
                ans = Math.max(ans, Math.abs(nums[i]));
            }else {
                set.add(nums[i]);
            }
        }
        return ans;
    }

    public int maxValueAfterReverse(int[] nums) {
        int ans = 0; int n = nums.length;
        for(int i=0; i<n-1; i++){
            ans += Math.abs(nums[i] - nums[i+1]);
        }
        int val = 0;
        for(int i=1; i<n-1; i++){
            val = Math.max(val, Math.abs(nums[0] - nums[i+1]) - Math.abs(nums[i] - nums[i+1]));
            val = Math.max(val, Math.abs(nums[n-1] - nums[i-1]) - Math.abs(nums[i] - nums[i-1]));
        }
        int b = Integer.MAX_VALUE; int c = Integer.MIN_VALUE;
        for(int i=0; i<n-1; i++){
            int x = nums[i]; int y = nums[i+1];
            c = Math.max(c, Math.min(x, y));
            b = Math.min(b, Math.max(x, y));
        }
        return ans + Math.max(val, 2*(c-b));
    }

    public static int getMaximumGenerated(int n) {
        int rnt = 0;
        int[] dp = new int[n+1];
        dp[1] = 1;
        for(int i=2; i<=n; i++){

            dp[i] = dp[i/2] + dp[i%2==0 ? 0 : i/2-1];
            rnt = Math.max(rnt, dp[i]);
        }

        return rnt;
    }


    public boolean queryString(String s, int n) {
        for(int i=1; i<=n; i++){
            String ss = Integer.toBinaryString(i);
            if(!s.contains(ss)){
                return false;
            }
        }
        return true;
    }

    public int numPairsDivisibleBy60(int[] time) {
        int rnt = 0;
        Map<Integer, List<Integer>> numMap = new HashMap<>();
        for (int tm : time) {
            int mod = tm % 60;
            int rela = mod == 0 ? 0 : 60 - mod;
            if(numMap.containsKey(rela)){
                rnt += numMap.get(rela).size();
            }
            if(numMap.containsKey(mod)){
                numMap.get(mod).add(tm);
            }else {
                numMap.put(mod, new ArrayList<>());
                numMap.get(mod).add(tm);
            }
        }
        return rnt;
    }

    public int smallestRepunitDivByK(int k) {
        int rnt = 0; int mod = 1;
        Set<Integer> modSet = new HashSet<>();
        do {
            if(modSet.contains(mod)){
                return -1;
            }
            modSet.add(mod);
            mod = mod % k;
            rnt++;
            if(mod == 0)return rnt;
            mod = mod * 10 + 1;
        }while (mod != 0);
        return rnt;
    }


    public int countTime(String time) {
        int rnt = 1;
        if(time.charAt(4) == '?'){
            rnt *= 10;
        }

        if(time.charAt(3) == '?'){
            rnt *= 6;
        }

        if(time.charAt(1) == '?' && time.charAt(0) == '?'){
            rnt *= 24;
        }else if(time.charAt(1) == '?' && time.charAt(0) != '?'){
            if(time.charAt(1) == '2'){
                rnt *= 4;
            }else {
                rnt *= 10;
            }
        }else if(time.charAt(1) != '?' && time.charAt(0) == '?'){
            if(time.charAt(1) < '5'){
                rnt *= 3;
            }else {
                rnt *= 2;
            }
        }
        return rnt;
    }
}
